package acwing.sort;

import java.util.Scanner;

/**
 * 给定一个长度为 n
 *  的整数数列，请你计算数列中的逆序对的数量。
 *
 * 逆序对的定义如下：对于数列的第 i
 *  个和第 j
 *  个元素，如果满足 i<j
 *  且 a[i]>a[j]
 * ，则其为一个逆序对；否则不是。
 *
 * 输入格式
 * 第一行包含整数 n
 * ，表示数列的长度。
 *
 * 第二行包含 n
 *  个整数，表示整个数列。
 *
 * 输出格式
 * 输出一个整数，表示逆序对的个数。
 *
 * 数据范围
 * 1≤n≤100000
 * ，
 * 数列中的元素的取值范围 [1,109]
 * 。
 *
 * 输入样例：
 * 6
 * 2 3 4 5 6 1
 * 输出样例：
 * 5
 */
public class inversionPairCount_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        System.out.println(inversionPairCount(arr, 0, arr.length - 1));

    }
    // 归并排序中两个子数组数字进行交换的次数就是逆序对
    public static long inversionPairCount(int[] arr,int left,int right){
        // 剪枝
        if (left >= right) return 0;
        // 1. 选择中间下标
        int mid = (left + right) / 2;
        // 2. 递归
        long res = 0;
        res += inversionPairCount(arr, left, mid) + inversionPairCount(arr, mid + 1, right);
        // 3. 排序
        int i = left,j = mid + 1,k = 0;
        int[] temp = new int[right - left + 1];
        while(i <= mid && j <= right){
            if(arr[i] <= arr[j]){
                temp[k++] = arr[i++];
            }
            else{
                temp[k++] = arr[j++];
                res += mid - i + 1;
            }
        }
        while(i <= mid){
            temp[k++] = arr[i++];
        }
        while(j <= right){
            temp[k++] = arr[j++];
        }
        for (i = left,k = 0; i <= right; i++,k++) {
            arr[i] = temp[k];
        }
        return res;
    }
}
